573B - Bear and Blocks - CodeForces Solution

#include <iostream>

const int MAX_N = 1e5 + 10;
const int INF = 1e9 + 10;

int n;

int value[MAX_N];
int minRight[MAX_N];
int minLeft[MAX_N];

int main() {

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &value[i]);
    }

    minLeft[0] = 0 - 0;
    for (int i = 1; i <= n + 1; i++) {
        minLeft[i] = std::min(minLeft[i-1], value[i] - i);
    }
    
    minRight[n+1] = 0 + (n+1);
    for (int i = n; i >= 0; i--) {
        minRight[i] = std::min(minRight[i+1], value[i] + i);
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        int life = std::min(minLeft[i] + i, minRight[i] - i);
        answer = std::max(answer, life);
    }

    printf("%d\n", answer);

}